package main

import (
	"math/rand"
)

// 思路一： 双指针二路分区（二向切分），快慢指针实现（mid慢， i快）
// 功能函数： 查找中间值（pivotKey）
func Partition(nums []int, l, r int) int {
	pivot := rand.Intn(r-l) + l
	// 还是选择最后一个元素，交换过去
	pivotKey := nums[pivot]
	nums[pivot], nums[r] = nums[r], nums[pivot]
	// 初始化为最后一个元素
	//pivotKey := nums[r]
	// 双指针， 二路分区。 mid 之前都小于 PivotKey， mid 之后都大于等于 pivotKey
	mid := l
	for i := l; i < r; i++ {
		if nums[i] < pivotKey {
			nums[mid], nums[i] = nums[i], nums[mid]
			mid += 1
		}
	}
	// 交换中间值到正确位置
	nums[mid], nums[r] = nums[r], nums[mid]
	return mid
}

// 思路二：三路快排分区， 对撞指针（d9区分出来三块区域，小于，等于，大于）
// 对撞指针， less, grate, i, 左右开区间， 中间是闭区间表示。
func Partition1(nums []int, l, r int) (less, grate int) {
	// 初始化为最后一个元素
	pivotKey := nums[r]
	// 对撞指针， less, grate, i
	less, grate = l, r-1
	for i := l; i <= grate; {
		if nums[i] < pivotKey {
			nums[less], nums[i] = nums[i], nums[less]
			less++
			i++
		} else if nums[i] > pivotKey {
			nums[grate], nums[i] = nums[i], nums[grate]
			grate-- // 这里后面不需要 i++。当前位置还需要接着判断
		} else {
			i++
		}
	}
	return
}

// 随机数随机 pivotKey 的值，效率更高。避免二叉树最坏性能,偏向一边，退化为链表
// 以二路分区为例
func Partition2(nums []int, l, r int) {
	pivot := rand.Intn(r-l) + l
	// 还是选择最后一个元素，交换过去
	pivotKey := nums[pivot]
	nums[pivot], nums[r] = nums[r], nums[pivot]
}

func QuickSort(nums []int, l, r int) {
	if l < r {
		mid := Partition(nums, l, r)
		QuickSort(nums, l, mid-1)
		QuickSort(nums, mid+1, r)
	}
}

func QuickSort1(nums []int, l, r int) {
	if l < r {
		less, grate := Partition1(nums, l, r)
		QuickSort(nums, l, less-1)
		QuickSort(nums, grate+1, r)
	}
}

// 还有一种传统的 对撞指针实现，python版本里有实现，比较复杂一些。
